package com.mlh.binarytree.search;

import com.mlh.binarytree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author 缪林辉
 * @date 2024/3/25 14:45
 * @DESCRIPTION
 */
public class PostorderTraversal {
    //方法一：递归
    public List<Integer> method1(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        recursion(root,res);
        return res;
    }
    public void recursion(TreeNode node,List<Integer>list){
        if(node==null){
            return;
        }
        recursion(node.left,list);
        recursion(node.right,list);
        list.add(node.val);
    }

    //方法二：栈
    //先将root入a栈
    //将a栈元素弹出 将其先左后右子节点压入a栈 最后再将该元素压入b栈
    //最后b栈弹出就是后序遍历的顺序
    public List<Integer> method2(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        Stack<TreeNode>a=new Stack<>();
        Stack<TreeNode>b=new Stack<>();
        List<Integer>res=new ArrayList<>();
        a.push(root);
        while (!a.isEmpty()){
            TreeNode node=a.pop();
            if(node.left!=null){
                a.push(node.left);
            }
            if (node.right!=null){
                a.push(node.right);
            }
            b.push(node);
        }
        while(!b.isEmpty()){
            res.add(b.pop().val);
        }
        return res;
    }

    public List<Integer> practice(TreeNode root){
        if(root==null){
            return new ArrayList<>();
        }
        List<Integer>res=new ArrayList<>();
        LinkedList<TreeNode>a=new LinkedList<>();
        LinkedList<TreeNode>b=new LinkedList<>();
        a.addLast(root);
        while(!a.isEmpty()){
            TreeNode node = a.pollLast();
            if(node.left!=null){
                a.addLast(node.left);
            }
            if(node.right!=null){
                a.addLast(node.right);
            }
            b.addLast(node);
        }
        while(!b.isEmpty()){
            res.add(b.pollLast().val);
        }
        return res;
    }

    public List<Integer> practice2(TreeNode root){
        LinkedList<TreeNode>a=new LinkedList<>(),b=new LinkedList<>();
        a.addLast(root);
        while(!a.isEmpty()){
            TreeNode temp=a.pollLast();
            if(temp.left!=null){
                a.addLast(temp.left);
            }
            if(temp.right!=null){
                a.addLast(temp.right);
            }
            b.addLast(temp);
        }
        List<Integer>res=new ArrayList<>();
        while(!b.isEmpty()){
            res.add(b.pollLast().val);
        }
        return res;
    }
}
